#include <iostream>

#define safe_delete(ptr) delete ptr; ptr = nullptr;
#define safe_delete_array(ptr) delete []ptr; ptr = nullptr;

class LRUCache
{
public:
    typedef int KeyType;
    typedef int ValueType;
    typedef struct CNode {
        KeyType key;
        ValueType value;
        struct CNode* last;
        struct CNode* next;
    } CacheNode;

    static const ValueType KEY_NOT_FOUND = -1;

private:
    int _capacity;
    int _size;
    CacheNode* _HeadOfList;
    CacheNode* _EndOfList;

    static const int DEFAULT_INIT_CAPACITY = 10;

private:
    bool AddNode(CacheNode* node);
    bool DetachNode(CacheNode* node);

public:
    LRUCache();
    LRUCache(int capacity);

    ~LRUCache();

    bool put(KeyType key, ValueType value);
    ValueType get(KeyType key);

    int size(void);
    int capacity(void);
    
};